/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/lfu-cache
   @Language: C++
   @Datetime: 19-03-13 09:59
   */

class LFUCache {
	unordered_map<int,pair<int,int> > cache;    // key, value, freq
	multimap<int,int> freq;                     // freq, key
	int capacity;
public:
	/*
	 * @param capacity: An integer
	 */
	LFUCache(int capacity) {
		 // do intialization if necessary
		 this->capacity = capacity;
		 cache.clear();
		 freq.clear();
	 }

	 /*
	  * @param key: An integer
	  * @param value: An integer
	  * @return: nothing
	  */
	 void set(int key, int value) {
		 // write your code here
		 unordered_map<int,pair<int,int> >::iterator ic=cache.find(key);
		 if(ic!=cache.end()){
			 // reset this key, but freq need +1
			 multimap<int,int>::iterator it=freq.find(ic->second.second);
			 for(; it!=freq.end() && it->second!=key; ++it);
			 freq.erase(it);
			 ic->second.first=value;
			 ic->second.second++;
			 freq.insert(make_pair(ic->second.second,key));
		 }
		 else{
			 if(cache.size()==capacity){
				 // erase least key
				 multimap<int,int>::iterator it=freq.begin();
				 cache.erase(it->second);
				 freq.erase(it);
			 }
			 // insert this key
			 cache[key]=make_pair(value,1);
			 freq.insert(make_pair(1,key));
		 }
	 }

	 /*
	  * @param key: An integer
	  * @return: An integer
	  */
	 int get(int key) {
		 // write your code here
		 unordered_map<int,pair<int,int> >::iterator ic=cache.find(key);
		 if(ic!=cache.end()){
			 // increasing freq
			 multimap<int,int>::iterator it=freq.find(ic->second.second);
			 for(; it!=freq.end() && it->second!=key; ++it);
			 freq.erase(it);
			 ic->second.second++;
			 freq.insert(make_pair(ic->second.second,key));
			 return ic->second.first;
		 }
		 return -1;
	 }
};
